package com.leetcode.algorithm.y19.m04;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * leetcode-cn.com
 * (done)454. 四数相加 II
 * (done)49. 字母异位词分组
 * (done)447. 回旋镖的数量
 * (done)149. 直线上最多的点数
 * @author: jie.deng
 * @time: 2019年4月26日 上午12:23:21
 */
public class MySolution0426 {
    
    /**
     * 454. 四数相加 II
     * 
     * 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
     * 
     * 为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。
     * 
     * 例如:
     * 
     * 输入:
     * A = [ 1, 2]
     * B = [-2,-1]
     * C = [-1, 2]
     * D = [ 0, 2]
     * 
     * 输出:
     * 2
     * 
     * 解释:
     * 两个元组如下:
     * 1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
     * 2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
     * @param A
     * @param B
     * @param C
     * @param D
     * @return
     */
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        // E = A + B，将 A + B 的每一种可能放入查找表
        Map<Integer, Integer> map1 = new HashMap<Integer, Integer>();
        for (int num : A) {
            map1.put(num, map1.get(num) == null ? 1 : 1 + map1.get(num));
        }
        Map<Integer, Integer> map2 = new HashMap<Integer, Integer>();
        for (int num : B) {
            map2.put(num, map2.get(num) == null ? 1 : 1 + map2.get(num));
        }
        Map<Integer, Integer> sum1Map = new HashMap<Integer, Integer>();
        for (Map.Entry<Integer, Integer> entry1 : map1.entrySet()) {
            int key1 = entry1.getKey();
            int value1 = entry1.getValue();
            for (Map.Entry<Integer, Integer> entry2 : map2.entrySet()) {
                int key = key1 + entry2.getKey();
                int value = value1 * entry2.getValue();
                sum1Map.put(key, sum1Map.get(key) == null ? value : value + sum1Map.get(key));
            }
        }
        // F = C + D，将 C + D 的每一种可能放入查找表
        map1 = new HashMap<Integer, Integer>();
        for (int num : C) {
            map1.put(num, map1.get(num) == null ? 1 : 1 + map1.get(num));
        }
        map2 = new HashMap<Integer, Integer>();
        for (int num : D) {
            map2.put(num, map2.get(num) == null ? 1 : 1 + map2.get(num));
        }
        Map<Integer, Integer> sum2Map = new HashMap<Integer, Integer>();
        for (Map.Entry<Integer, Integer> entry1 : map1.entrySet()) {
            int key1 = entry1.getKey();
            int value1 = entry1.getValue();
            for (Map.Entry<Integer, Integer> entry2 : map2.entrySet()) {
                int key = key1 + entry2.getKey();
                int value = value1 * entry2.getValue();
                sum2Map.put(key, sum2Map.get(key) == null ? value : value + sum2Map.get(key));
            }
        }

        // E + F = 0 ? 对于查找表E中的每一个元素a，查找 target - a 是否存在于F。
        int cnt = 0;
        for (Map.Entry<Integer, Integer> entry : sum1Map.entrySet()) {
            int key = entry.getKey();
            int value = entry.getValue();
            if (sum2Map.containsKey(-key)) {
                cnt += value * sum2Map.get(-key);
            }
        }
        return cnt;
    }
    
    /**
     * 49. 字母异位词分组
     * 
     * 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
     * 
     * 示例:
     * 
     * 输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
     * 输出:
     * [
     *   ["ate","eat","tea"],
     *   ["nat","tan"],
     *   ["bat"]
     * ]
     * 说明：
     * 
     * 所有输入均为小写字母。
     * 不考虑答案输出的顺序。
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) {
            return new ArrayList<List<String>>();
        }
        int len = strs.length;
        int[][] cntArr = new int[len][26]; // 26个小写字母
        for (int i = 0; i < len; i++) {
            String str = strs[i];
            int length = str.length();
            for (int j = 0; j < length; j++) {
                cntArr[i][str.charAt(j) - 'a']++; // 记录26个小写字母出现的次数
            }
        }
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (int i = 0; i < len; i++) {
            String key = Arrays.toString(cntArr[i]); // 26个小写字母出现的次数组成的序列作为key，key相同的字符串即为字母异位词
            List<String> val = map.get(key);
            if (val == null) {
                val = new ArrayList<String>();
                map.put(key, val);
            }
            val.add(strs[i]);
        }
        return new ArrayList<List<String>>(map.values());
    }
    
    /**
     * 447. 回旋镖的数量
     * 
     * 给定平面上 n 对不同的点，“回旋镖” 是由点表示的元组 (i, j, k) ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。
     * 
     * 找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。
     * 
     * 示例:
     * 
     * 输入:
     * [[0,0],[1,0],[2,0]]
     * 
     * 输出:
     * 2
     * 
     * 解释:
     * 两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
     * @param points
     * @return
     */
    public int numberOfBoomerangs(int[][] points) {
        int len = points.length;
        int[][] disArr = new int[len][len]; // disArr[i][j] 表示
                                            // points[i]和points[j]之间的距离
        for (int i = 0; i < len - 1; i++) {
            int[] pointI = points[i];
            for (int j = i + 1; j < len; j++) {
                int[] pointJ = points[j];
                int dis = (pointI[0] - pointJ[0]) * (pointI[0] - pointJ[0])
                        + (pointI[1] - pointJ[1]) * (pointI[1] - pointJ[1]);
                disArr[i][j] = dis;
                disArr[j][i] = dis;
            }
        }

        int cntSum = 0;
        for (int i = 0; i < len; i++) {
            Map<Integer, Integer> map = new HashMap<Integer, Integer>(); // key=距离，value=距离出现的次数
            for (int j = 0; j < len; j++) {
                if (i == j || disArr[i][j] == 0) {
                    continue;
                }
                map.put(disArr[i][j], map.get(disArr[i][j]) == null ? 1 : 1 + map.get(disArr[i][j]));
            }
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                Integer cnt = entry.getValue();
                cntSum += cnt * (cnt - 1);
            }
        }
        return cntSum;
    }
    
    /**
     * 149. 直线上最多的点数
     * 
     * 给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。
     * 
     * 示例 1:
     * 
     * 输入: [[1,1],[2,2],[3,3]]
     * 输出: 3
     * 解释:
     * ^
     * |
     * |        o
     * |     o
     * |  o  
     * +------------->
     * 0  1  2  3  4
     * 示例 2:
     * 
     * 输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
     * 输出: 4
     * 解释:
     * ^
     * |
     * |  o
     * |     o        o
     * |        o
     * |  o        o
     * +------------------->
     * 0  1  2  3  4  5  6
     * @param points
     * @return
     */
    public int maxPoints(int[][] points) {
        int len = points.length;
        // pairArr[i][j]表示points[i]和points[j]组成的直线与坐标横轴的倾斜角的 高和宽 。
        Pair[][] pairArr = new Pair[len][len];

        for (int i = 0; i < len; i++) {
            int[] pointI = points[i];
            for (int j = i; j < len; j++) {
                int[] pointJ = points[j];
                if (pointI[1] == pointJ[1] && pointI[0] == pointJ[0]) { // 重合的点
                    pairArr[i][j] = new Pair(0, 0);
                    continue;
                }
                if (pointI[0] == pointJ[0]) {
                    pairArr[i][j] = new Pair(0, 1);
                    pairArr[j][i] = new Pair(0, 1);
                } else if (pointI[1] == pointJ[1]) {
                    pairArr[i][j] = new Pair(1, 0);
                    pairArr[j][i] = new Pair(1, 0);
                } else {
                    int x = 0;
                    int y = 0;
                    if (pointI[0] > pointJ[0]) {
                        x = pointI[0] - pointJ[0];
                        y = pointI[1] - pointJ[1];
                    } else {
                        x = pointJ[0] - pointI[0];
                        y = pointJ[1] - pointI[1];
                    }
                    // 求x、y的最大公约数
                    int x1 = Math.abs(x);
                    int y1 = Math.abs(y);
                    if (x1 < y1) {
                        x1 = x1 ^ y1;
                        y1 = x1 ^ y1;
                        x1 = x1 ^ y1;
                    }
                    int z = Math.min(x1, y1);
                    while (!(x1 % z == 0 && y1 % z == 0)) {
                        z = x1 - y1;
                        while (z > y1) {
                            z -= y1;
                        }
                        if (!(x1 % z == 0 && y1 % z == 0)) {
                            x1 = y1;
                            y1 = z;
                        }
                    }
                    if (z != 1) {
                        x = x / z;
                        y = y / z;
                    }
                    pairArr[i][j] = new Pair(x, y);
                    pairArr[j][i] = new Pair(x, y);
                }
            }
        }

        int max = 0;
        for (int i = 0; i < len; i++) {
            int sameCnt = 0; // 重合的点的数量
            Map<Pair, Integer> pairMap = new HashMap<Pair, Integer>(); // key=弧度，value=弧度出现的次数
            for (int j = 0; j < len; j++) {
                if (new Pair(0, 0).equals(pairArr[i][j])) {
                    sameCnt++;
                } else {
                    pairMap.put(pairArr[i][j], pairMap.get(pairArr[i][j]) == null ? 1 : 1 + pairMap.get(pairArr[i][j]));
                }
            }
            int cntMax = 0;
            Collection<Integer> values = pairMap.values();
            for (Integer num : values) {
                cntMax = Math.max(cntMax, num);
            }
            max = Math.max(max, cntMax + sameCnt);
        }
        return max;
    }
    
    class Pair{
        int key;
        int value;
        public Pair(int key, int value) {
            super();
            this.key = key;
            this.value = value;
        }
        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + getOuterType().hashCode();
            result = prime * result + key;
            result = prime * result + value;
            return result;
        }
        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Pair other = (Pair) obj;
            if (!getOuterType().equals(other.getOuterType()))
                return false;
            if (key != other.key)
                return false;
            if (value != other.value)
                return false;
            return true;
        }
        private MySolution0426 getOuterType() {
            return MySolution0426.this;
        }
    }
    
    public static void main(String[] args) {
        System.out.println(Math.atan2(2, 0));
        System.out.println(Math.atan2(-2, 0));
        System.out.println(Math.atan2(0, 2));
        System.out.println(Math.atan2(0, -2));
        System.out.println(Math.atan2(2, -2));
        System.out.println(Math.atan2(-2, 2));
        System.out.println(Math.atan2(2, 2));
        System.out.println(Math.atan2(-2, -2));
    }
}
